package two.chapter_2.c2_2;

import edu.princeton.cs.algs4.StdOut;
import two.chapter_2.c2_1.Sortable;

/**
 * 自底向上的归并排序：
 * 首先把一个长度的数组两两合并
 * 再把长度为2的数组两两合并
 * 接着长度为4的数组两两合并，直到结束。
 *
 * @param <Item>
 */
public class MergeBUSort<Item extends Comparable<Item>> extends Sortable<Item> {

    private Object[] aux;

    @Override
    public void sort(Item[] items) {
        int N = items.length;
        aux = new Object[N];
        for (int sz = 1;sz<N;sz=sz+sz){
            //StdOut.print(sz+" ");
            for (int i=0;i<N-sz;i+=sz+sz){
                int lo=i;
                int mid=lo+sz-1;
                int hi=Math.min(lo+sz*2-1,N-1);
                merge(items,lo,mid,hi);
            }
        }
    }

    private void merge(Item[] items, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            aux[i] = items[i];
        }

        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {//i指针走完
                items[k] = (Item) aux[j++];
            } else if (j > hi) {//j指针走完
                items[k] = (Item) aux[i++];
            } else if (less((Item) aux[i], (Item) aux[j])) {
                items[k] = (Item) aux[i++];
            } else {
                items[k] = (Item) aux[j++];
            }
        }
    }
}
